﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution75
{
    public void SortColors2(int[] nums)//排序算法
    {
        //Array.Sort(nums);

        Quick(nums,0,nums.Length-1);


    }  public void SortColorsSingle(int[] nums)//单个指针
    {
        int len=nums.Length;
        int head = 0;
        for (int i=0; i<len; i++)
        {

            if (nums[i] == 0)//把所有的0放到数组前面
            {
            swap(nums,head,i);
                head++;
            }
        }

        for (int i = 0; i < len; i++)
        {

            if (nums[i] == 1)//把所有的1放到数组中间
            {
                swap(nums, head, i);
                head++;
            }
        }
    }public void SortColors(int[] nums)//双指针
    {
        int len=nums.Length;
        int p0 = 0;
        int p1 = 0;
        for (int i=0; i<len; i++)
        {

            if (nums[i] == 0)//把所有的0放到数组前面
            {
            swap(nums, p0, i);
                p0++;
                if (p0 < p1)
                {
                    swap(nums, p1, i);
                }

                
                p1++;
            }else
            if (nums[i] == 1)//把所有的1放到数组中间
            {
                swap(nums, p1, i);

                p1++;
                
            }
        }

       
    }

    private void Quick(int[] nums,int left,int right)
    {
        //int pivot = left;
        //这个是记录值，而不是index，index不会变，但是nums[pivot]会变
        int pivotValue = nums[left];
        int oldleft = left;
        int oldright = right;
        while (left < right)
        {
            Console.WriteLine(left);
            Console.WriteLine(nums[left]);
            Console.WriteLine(pivotValue);
            while (left < right&&nums[right] >= pivotValue)
            { right--; }
            swap(nums, left, right);
            while (left < right && nums[left] <= pivotValue) //
            { left++;
                Console.WriteLine(nums[left]);
                Console.WriteLine("pivotValue"+pivotValue);
            }
         

            swap(nums, left, right);
        }
        //没有递归的中止条件
        if (oldleft < left)
        {
            Quick(nums, oldleft, left - 1);
        }
        if(oldright > right)
        {
            Quick(nums, right + 1, oldright);
        }
        
        
    }
    private void Quick1(int[] nums, int left, int right)
    {
        if (left < right)
        {
            int pivot = GetPivot(nums, left, right);
 Quick(nums, left, pivot-1);
 Quick(nums, pivot+1, right);
        }


    }

    private int GetPivot(int[] nums, int left, int right)
    {
        int pivotValue = nums[left];
       
        while (left < right)
        {
            Console.WriteLine(left);
            Console.WriteLine(nums[left]);
            Console.WriteLine(pivotValue);
            while (left < right && nums[right] >= pivotValue)
            { right--; }
            swap(nums, left, right);
            while (left < right && nums[left] <= pivotValue) //
            {
                left++;
               
            }

            swap(nums, left, right);
        }
        return left;
    }

    private void swap(int[] nums, int left, int right)
    {
        Console.WriteLine("swap一次"+left+"右边"+right);
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
class Program75
{

    static void Main75(string[] args)
    {
        //int[] colors = { 2, 0, 2, 1, 1, 0 };
        int[] colors = { 1,0};
        //int[] colors = { 53, 17, 78, 09, 45, 65, 87, 32 };

        Solution75 solution = new Solution75();
        solution.SortColors(colors);
        for (int i = 0; i < colors.Length; i++)
        {
            Console.WriteLine(colors[i]);
        }
        

    }

   

}
